package leetcode.code300;

import java.util.Stack;

public class Solution extends Solution300 {

	@Override
	public int lengthOfLIS(int[] nums) {
		// [10,9,2,5,3,7,101,18]
		// [0,1,0,3,2,3]
		// [4,10,4,3,8,9]
		Stack<Integer> s1 = new Stack<>();
		Stack<Integer> s2 = new Stack<>();
		s1.add(nums[0]);
		for (int i = 1; i < nums.length; i++) {
			if (s1.peek() < nums[i]) {
				s1.add(nums[i]);
			} else if (s1.peek() > nums[i] && !s1.contains(nums[i])) {
				while (!s1.isEmpty() && s1.peek() >= nums[i]) {
					s2.add(s1.pop());
				}
				s2.pop();
				s1.add(nums[i]);
				while (!s2.isEmpty()) {
					s1.add(s2.pop());
				}
			}
		}
		return s1.size();
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
